package Solution101_200.problem109.ConvertSortedListtoBinarySearchTree;

import common.ListNode;
import common.TreeNode;

/**
 * @program Leetcode
 * @description:
 * @author: lishangsheng
 * @create: 2019/07/11 17:10
 */
public class BetterSolution {
    public TreeNode sortedListToBST(ListNode head) {
        int length = 0;
        ListNode cur = head;
        while (cur != null) {
            length++;
            cur = cur.next;
        }
        return wrapper(head, 0, length);
    }

    private TreeNode wrapper(ListNode head, int left, int right) {
        if (left >= right) {
            return null;
        } else {
            int mid = left + (right - left) / 2;
            int cnt = 0;
            ListNode cur = head;
            ListNode prev = null;
            while (cnt != mid && cur != null) {
                prev = cur;
                cur = cur.next;
                cnt++;
            }
            TreeNode root = new TreeNode(cur.val);
            if (prev != null) {
                prev.next = null;
            }
            root.left = wrapper(head, left, mid);
            root.right = wrapper(cur.next, 0, right - mid - 1);
            return root;
        }
    }
}
